#pragma once
#include<iostream>
#include <queue>
#include"Color.h"
#include"FastBB.h"
using namespace std;

class Framework
{
private:
    int **Graph;
    int *degree;
    int bi_index;
    int graph_size;
    int k;
    double alpha,beta;

    int **pG;
    int *pd;
    int pb, pgs;
    int top_K;
    int theta_l,theta_r;
    bool isTwoHopReduce;

    int *temp_index;
    int *temp_deg;
    int *re_temp_index;
    int *t_count;

    int temp_i,temp_j,temp_k, temp_node, temp_node2;
    
    void Record_dec();

public:
    Framework(int **Graph, int *degree, int graph_size, int bi_index, double alpha, double beta, int theta_l, int theta_r, int top_K, bool isTwoHopReduce);
    ~Framework();
    void Two_hop(int l, int r, bool isTwoHopReduce);
    void Two_hop_n(int l, int r, bool isTwoHopReduce);
    void Two_hop_n2(int l, int r, bool isTwoHopReduce);
    void Two_hop_n3(int l, int r, bool isTwoHopReduce);
    void PBIE();
    int edges,v_r,v_l;
    subgraph MaxBP;
    priority_queue<subgraph,vector<subgraph>,greater<subgraph>> res_top_k;
};

Framework::Framework(int **Graph, int *degree, int graph_size, int bi_index, double alpha, double beta, int theta_l, int theta_r, int top_K, bool isTwoHopReduce)
{
    this->Graph=Graph;
    this->degree=degree;
    this->graph_size=graph_size;
    this->bi_index=bi_index;
    this->alpha=alpha;
    this->beta=beta;
    this->theta_l=theta_l;
    this->theta_r=theta_r;
    this->top_K=top_K;
    this->pgs=0;
    this->isTwoHopReduce=isTwoHopReduce;

    temp_index=new int[graph_size];
    temp_deg=new int[graph_size];
    re_temp_index=new int[graph_size];
    t_count=new int[graph_size];

    for(int i=graph_size-1;i>=0;--i){
        temp_index[i]=0;
        temp_deg[i]=0;
        re_temp_index[i]=0;
        t_count[i]=0;
    }
    
}

Framework::~Framework()
{
}


void Framework::PBIE(){
    int current=0; 
    int maxLdeg=0, maxRdeg=0;
    for(temp_i=bi_index-1;temp_i>=0;--temp_i){
        if(degree[temp_i]>maxLdeg){
            maxLdeg=degree[temp_i];
        }
    }
    for(temp_i=graph_size-1;temp_i>=0;--temp_i){
        if(degree[temp_i]>maxRdeg){
            maxRdeg=degree[temp_i];
        }
    }
    int low_l, low_r;
    cout<<"maxLdeg:"<<maxLdeg<<endl;
    cout<<"maxRdeg:"<<maxRdeg<<endl;
    low_l=int(maxRdeg/beta)>(graph_size-bi_index)?(graph_size-bi_index):int(maxRdeg/beta);
    cout<<"start low_l::"<<low_l<<endl;
    int last_v;
    int temp_flag=1;
    priority_queue<subgraph,vector<subgraph>,greater<subgraph>> top_k;
    while(low_l>theta_l && temp_flag){
        if(low_l==theta_l)temp_flag=0;
        last_v=low_l;
        low_r=current-low_l<theta_r?theta_r:current-low_l;
        low_l=low_l/2<theta_l?theta_l:low_l/2;
        cout<<"low_R:"<<low_r<<" low_L:"<<low_l<<"  ";
        Two_hop_n3(low_l, low_r, isTwoHopReduce);
        if(pgs!=0){      
            BKMB bkmb(pG,pd,pgs,pb,alpha,beta,low_l,low_r,top_K,top_k);
            bkmb.myset=last_v;      //上一轮的下界的大小
            bkmb.current=current;     //当前最好解
            bkmb.re_temp_index=re_temp_index;  
            bkmb.BKmb();
            top_k=bkmb.top_k;
            if(!top_k.empty())
                current=bkmb.top_k.top().current;
            else if(current)
                current=0;
        }
    }
    
    
    res_top_k=top_k;
}

void Framework::Record_dec(){

    int maxLdeg=0;
    int maxRdeg=0;
    for(temp_i=bi_index-1;temp_i>=0;--temp_i){
        if(degree[temp_i]>maxLdeg){
            maxLdeg=degree[temp_i];
        }
    }
    for(temp_i=graph_size-1;temp_i>=bi_index;--temp_i){
        if(degree[temp_i]>maxRdeg){
            maxRdeg=degree[temp_i];
        }
    }

    int *binL=new int[maxLdeg+1];
    int *binR=new int[maxRdeg+1];

    for(temp_i=maxLdeg;temp_i>=0;--temp_i){
        binL[temp_i]=0;
    }
    for(temp_i=maxRdeg;temp_i>=0;--temp_i){
        binR[temp_i]=0;
    }
    for(temp_i=graph_size-1;temp_i>=bi_index;--temp_i){
        binR[degree[temp_i]]+=1;
    }
    for(temp_i=bi_index-1;temp_i>=0;--temp_i){
        binL[degree[temp_i]]+=1;
    }

    temp_i=0;
    for(temp_j=0;temp_j<=maxLdeg;++temp_j){
        temp_k=binL[temp_j];
        binL[temp_j]=temp_i;
        temp_i+=temp_k;
    }
    temp_i=0;
    for(temp_j=0;temp_j<=maxRdeg;++temp_j){
        temp_k=binR[temp_j];
        binR[temp_j]=temp_i;
        temp_i+=temp_k;
    }

    int *pos=new int[graph_size+1];
    int *vert=new int[graph_size+1];
    int *G_temp=new int[graph_size];

    for(temp_i=graph_size;temp_i>=0;--temp_i){
        pos[temp_i]=0;
        vert[temp_i]=0;

    }
    for(temp_i=graph_size-1;temp_i>=0;--temp_i){
        G_temp[temp_i]=degree[temp_i];
    }
    for(temp_i=0;temp_i<bi_index;++temp_i){
        pos[temp_i]=binL[degree[temp_i]];
        vert[pos[temp_i]]=temp_i;
        binL[degree[temp_i]]+=1;
    }
    for(temp_i=maxLdeg;temp_i>=1;--temp_i){
        binL[temp_i]=binL[temp_i-1];
    }
    binL[0]=1;
    
    for(temp_i=0;temp_i<bi_index;++temp_i){
        temp_node=vert[temp_i];
        for(temp_j=degree[temp_node]-1;temp_j>=0;--temp_j){
            temp_node2=Graph[temp_node][temp_j];
            if(G_temp[temp_node2]>G_temp[temp_node]){
                int du=G_temp[temp_node2]; int pu=pos[temp_node2];
                int pw=binL[du]; int w=vert[pw];
                if(temp_node2!=w){
                    pos[temp_node2]=pw; vert[pu]=w;
                    pos[w]=pu; vert[pw]=temp_node2;
                }
                binL[du]+=1;
                G_temp[temp_node2]-=1;
            }
        }
    }
}




void Framework::Two_hop_n3(int low_l, int low_r, bool isTwoHopReduce){

    int l = ceil(low_r*alpha), r = ceil(low_l*beta);
    //删除的是度数小于l和r的点
    for(temp_i=graph_size-1;temp_i>=0;--temp_i){
        temp_index[temp_i]=1;
        temp_deg[temp_i]=degree[temp_i];
    }
    bool flag=true; 
    bool flag_2hop=true;
    int countL=0, countR=0;
    int t_neighbor=0;
    int ceshi_t_neigb=0;
    int temp_a=5, temp_b=0;
    int l2=2*l-low_r -1,r2=2*r-low_l -1;
    unordered_map<int,int> mmap;
    
    time_t s1 = clock();

    double time_1, time_2, time_3;
    
    while(flag_2hop && temp_a--){
        while(flag){
            
            flag=false;
            for(temp_i=bi_index-1;temp_i>=0;--temp_i){
                if(temp_index[temp_i]==0||temp_deg[temp_i]>=l-1) continue;
                temp_index[temp_i]=0;     //标记被删除的点
                flag=true;
                countL++;     //记录删点个数
                for(temp_j=degree[temp_i]-1;temp_j>=0;--temp_j){
                    --temp_deg[Graph[temp_i][temp_j]];
                }
            }
            for(temp_i=bi_index;temp_i<graph_size;++temp_i){
                if(temp_index[temp_i]==0||temp_deg[temp_i]>=r-1) continue;
                flag=true;
                countR++;
                temp_index[temp_i]=0;
                for(temp_j=degree[temp_i]-1;temp_j>=0;--temp_j){
                    --temp_deg[Graph[temp_i][temp_j]];
                }
            }
        }
        if(!isTwoHopReduce)break;
        flag_2hop=false;
        Color color(bi_index);
        for(temp_i=bi_index-1;temp_i>=0;--temp_i){
            if(temp_index[temp_i]==0)continue;
            t_neighbor=0;
            mmap.clear();
            
            for(temp_j=degree[temp_i]-1;temp_j>=0;--temp_j){
                temp_node=Graph[temp_i][temp_j];
                if(temp_index[temp_node]==0)continue;
                for(temp_k=degree[temp_node]-1;temp_k>=0;--temp_k){
                    temp_b=Graph[temp_node][temp_k];
                    if(temp_b>=temp_i)continue;
                    if(temp_index[temp_b]!=0){
                        //t_count[temp_b]++;
                        mmap[temp_b]++;
                    }
                }
            }
            
            for(auto m: mmap){
                if(m.second>=l2)color.constructGraph(temp_i, m.first);
            }
            
            
        }
        vector<int> neighbor_count=color.greedyColoring();
        for(temp_i=bi_index-1;temp_i>=0;--temp_i){
            if(temp_index[temp_i]==0)continue;
            if(neighbor_count[temp_i]<low_l-1){
                flag_2hop=true;flag=true;
                countL++;
                temp_index[temp_i]=0;
                for(temp_j=degree[temp_i]-1;temp_j>=0;--temp_j){
                    --temp_deg[Graph[temp_i][temp_j]];
                }
            }
        }

        color.reassign(graph_size-bi_index);
        for(temp_i=bi_index;temp_i<graph_size;++temp_i){
            if(temp_index[temp_i]==0)continue;
            t_neighbor=0;
            mmap.clear();
            
            for(temp_j=degree[temp_i]-1;temp_j>=0;--temp_j){
                temp_node=Graph[temp_i][temp_j];
                if(temp_index[temp_node]==0)continue;
                for(temp_k=degree[temp_node]-1;temp_k>=0;--temp_k){
                    temp_b=Graph[temp_node][temp_k];
                    if(temp_b<=temp_i)continue;
                    if(temp_index[temp_b]!=0){
                        mmap[temp_b]++;
                    }
                }
            }
            for(auto m: mmap){
                if(m.second>=r2)color.constructGraph(temp_i-bi_index,m.first-bi_index);
            }
        }
        neighbor_count.clear();
        neighbor_count=color.greedyColoring();
        for(temp_i=bi_index;temp_i<graph_size;++temp_i){
            if(temp_index[temp_i]==0)continue;
            if(neighbor_count[temp_i-bi_index]<low_r-1){
                flag_2hop=true;flag=true;
                countR++;
                temp_index[temp_i]=0;
                for(temp_j=degree[temp_i]-1;temp_j>=0;--temp_j){
                    --temp_deg[Graph[temp_i][temp_j]];
                }
            }
        }
    }

    if(pgs!=0){
        for(temp_i=pgs-1;temp_i>=0;--temp_i){
            delete [] pG[temp_i];
        }
    
        delete []pd;
        delete []pG;
    }
    
    
    pgs=graph_size-countL-countR;    //还剩下的点数量
    cout<<"---after reduce: "<<pgs<<"  L:"<<bi_index-countL<<endl; 
    if(pgs==0) return;
    pd=new int[pgs];
    temp_i=1;

    for(temp_j=0;temp_j<graph_size;++temp_j){
        if(temp_index[temp_j]){
            temp_index[temp_j]=temp_i;
            ++temp_i;
        }
    }   //给每个剩下的点标记序号

    for(temp_j=0;temp_j<graph_size;++temp_j){
        if(temp_index[temp_j]){
            temp_node=temp_index[temp_j]-1;
            re_temp_index[temp_node]=temp_j;
        }
    }     //temp_node记录删除点后的新索引，re_temp_index记录点在原本的图上的索引

    pb=bi_index-countL;      //左边剩点
    pG=new int*[pgs];
    for(temp_i=0;temp_i<graph_size;++temp_i){
        temp_node=temp_index[temp_i]-1;
        if(temp_node>=0){
            pd[temp_node]=temp_deg[temp_i];    //度数新数组
            pG[temp_node]=new int[temp_deg[temp_i]];    //新图创建
            temp_k=0;
            for(temp_j=0;temp_j<degree[temp_i];++temp_j){
                temp_node2=Graph[temp_i][temp_j];
                if(temp_index[temp_node2]){      //没删就放到新图
                    pG[temp_node][temp_k]=temp_index[temp_node2]-1;   
                    temp_k++;
                }
            }
        }
    }  
    
}
